Intra prediction is a key component of image and video compression methods. Given observations, or known samples in a spatial neighborhood, the goal of intra prediction is to estimate unknown pixels of the block to be predicted.
For example, in H.264/AVC Karsten Suhring, H.264/AVC Reference Software, http://iphome.hhi.de/suehring/tml/download/, the book of I. E. Richardson titled <<H.264 and MPEG-4 video compression>> published in J. Wiley & Sons in September 2003, there are two intra-frame prediction types called Intra-16×16, Intra-8×8 and Intra-4×4. Each 4×4 block is predicted from prior encoded (and reconstructed) pixels of spatially neighboring blocks. In addition to the so-called “DC” mode which consists in predicting the entire 4×4 block from the mean of neighboring pixels, eight directional prediction modes have been specified. The prediction is done by simply “propagating (interpolating)” the pixel values along the specified direction. This approach is suitable in the presence of contours when the directional mode chosen corresponds to the orientation of the contour. However, it fails in more complex textured areas.
An alternative spatial prediction method based on template matching (TM) has been described by T. K. Tan, C. S. Boon, and Y. Suzuki, “Intra prediction by template matching,” in Proc. IEEE Int. Conf Image Pmcess., 2006, pp. 1693-1696. A so-called template is formed by previously encoded pixels in a close neighborhood of the block to be predicted. The best match between the template of the block to be predicted and candidate texture patches of same shape as the template, within a causal search window, allows finding the predictor of the block to be predicted.
Turkan et al. (M. Turkan and C. Guillemot, “Image prediction based on neighbor embedding methods,” IEEE Trans. on Image Processing, vol. 21, no. 4, pp. 1885-1R9R, April 2012.) have considered neighbor embedding solutions to address the problem. An Intra prediction method using neighbor embedding first search, within a window in the causal part of the image, for the K-Nearest Neighbors (K-NN) to the template pixels of the input patch to be predicted. They then search for the best approximation of the template pixels by a linear combination of their K-NN. The method then varies in the way the coefficients of the linear combinations are computed, using similarity weights with a Gaussian kernel as in a so-called NLM-inspired method (A. Wong and J. Orchard, “A nonlocal-means approach to exemplar-based inpainting,” in iEEE int Conf image Process. (ICIP), 2006, pp. 2600-2603.), or using least squares approximations under a sum-to-one constraint for the weights as in a so-called LLE-based method (S. Roweis and L. Saul, “Nonlinear dimensionality reduction by locally linear embedding,” Science, vol. 290, pp. 2323-2326, December 2000.), or under a positivity constraint as in a NMF-based approach (D. D. Lee and H. S. Seung, “Algorithms for non-negative matrix factorization,” Advances in Neural Information Process. Syst. (NIPS), 2000.).
Significant gains have been shown when comparing the neighbor-embedding based intra prediction against a simple template matching.
However, the K-NN patches used for the linear approximation of the input patch has obviously a strong impact on the performance. Searching for the K-NN by computing a distance on the template pixels may not lead to the best blocks for approximating the unknown pixels of the block to be predicted, especially in the case where there are discontinuities between the template and the current block.